<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<head>
    <title>Jumper documentation</title>
    <link rel="stylesheet" href="../ldoc.css" type="text/css" />
</head>
<body>

<div id="container">

<div id="product">
	<div id="product_logo"></div>
	<div id="product_name"><big><b></b></big></div>
	<div id="product_description"></div>
</div> <!-- id="product" -->


<div id="main">


<!-- Menu -->

<div id="navigation">
<br/>
<h1>Jumper</h1>

<ul>
  <li><a href="../index.html">Index</a></li>
</ul>

<h2>Contents</h2>
<ul>
<li><a href="#Class_heap_">Class heap </a></li>
</ul>


<h2>Modules</h2>
<ul>
  <li><strong>core.bheap</strong></li>
  <li><a href="../modules/core.heuristics.html">core.heuristics</a></li>
  <li><a href="../modules/core.node.html">core.node</a></li>
  <li><a href="../modules/core.path.html">core.path</a></li>
  <li><a href="../modules/grid.html">grid</a></li>
  <li><a href="../modules/pathfinder.html">pathfinder</a></li>
</ul>
<h2>Examples</h2>
<ul>
  <li><a href="../examples/annotatedpathing.lua.html">annotatedpathing.lua</a></li>
  <li><a href="../examples/customheuristics.lua.html">customheuristics.lua</a></li>
  <li><a href="../examples/makeclearance.lua.html">makeclearance.lua</a></li>
  <li><a href="../examples/simpleexample.lua.html">simpleexample.lua</a></li>
</ul>

</div>

<div id="content">

<h1>Module <code>core.bheap</code></h1>

<p>A light implementation of Binary heaps data structure.</p>
<p> While running a search, some search algorithms (Astar, Dijkstra, Jump Point Search) have to maintains
 a list of nodes called <strong>open list</strong>. Retrieve from this list the lowest cost node can be quite slow,
 as it normally requires to skim through the full set of nodes stored in this list. This becomes a real
 problem especially when dozens of nodes are being processed (on large maps). </p>

<p> The current module implements a <a href="http://www.policyalmanac.org/games/binaryHeaps.htm">binary heap</a>
 data structure, from which the search algorithm will instantiate an open list, and cache the nodes being
 examined during a search. As such, retrieving the lower-cost node is faster and globally makes the search end
 up quickly.</p>

<p> This module is internally used by the library on purpose.
 It should normally not be used explicitely, yet it remains fully accessible.</p>

<h2><a href="#Class_heap_">Class heap </a></h2>
<table class="function_list">
	<tr>
	<td class="name" nowrap><a href="#heap:empty">heap:empty&nbsp;()</a></td>
	<td class="summary">Checks if a <a href="../modules/core.bheap.html#Class_heap">heap</a>  is empty</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#heap:clear">heap:clear&nbsp;()</a></td>
	<td class="summary">Clears the <a href="../modules/core.bheap.html#Class_heap">heap</a>  (removes all items queued in the heap)</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#heap:push">heap:push&nbsp;(item)</a></td>
	<td class="summary">Adds a new item in the <a href="../modules/core.bheap.html#Class_heap">heap</a> </td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#heap:pop">heap:pop&nbsp;()</a></td>
	<td class="summary">Pops from the <a href="../modules/core.bheap.html#Class_heap">heap</a> .</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#heap:heapify">heap:heapify&nbsp;( [item])</a></td>
	<td class="summary">Restores the <a href="../modules/core.bheap.html#Class_heap">heap</a>  property.</td>
	</tr>
</table>

<br/>
<br/>


    <h2><a name="Class_heap_"></a>Class heap </h2>
    The <a href="../modules/core.bheap.html#Class_heap">heap</a>  class.<br/>
 This class is callable.
 <em>Therefore,</em> <code>heap(...)</code> <em>is used to instantiate new heaps</em>.
    <dl class="function">
    <dt>
    <a name = "heap:empty"></a>
    <strong>heap:empty&nbsp;()</strong>
    </dt>
    <dd>
    Checks if a <a href="../modules/core.bheap.html#Class_heap">heap</a>  is empty


    <h3>Usage:</h3>
    <ul>
        <pre class="example">
 if myHeap:empty() then
   print('Heap is empty!')
 end</pre>
    </ul>

    <h3>Returns:</h3>
    <ol>

          <span class="types"><a class="type" href="http://www.lua.org/manual/5.1/manual.html#2.2">bool</a></span>
        <strong>true</strong> of no item is queued in the heap, <strong>false</strong> otherwise
    </ol>


</dd>
    <dt>
    <a name = "heap:clear"></a>
    <strong>heap:clear&nbsp;()</strong>
    </dt>
    <dd>
    Clears the <a href="../modules/core.bheap.html#Class_heap">heap</a>  (removes all items queued in the heap)


    <h3>Usage:</h3>
    <ul>
        <pre class="example">myHeap:clear()</pre>
    </ul>

    <h3>Returns:</h3>
    <ol>

          <span class="types"><a class="type" href="../modules/core.bheap.html#Class_heap">heap</a></span>
        self (the calling <a href="../modules/core.bheap.html#Class_heap">heap</a>  itself, can be chained)
    </ol>


</dd>
    <dt>
    <a name = "heap:push"></a>
    <strong>heap:push&nbsp;(item)</strong>
    </dt>
    <dd>
    Adds a new item in the <a href="../modules/core.bheap.html#Class_heap">heap</a>

    <h3>Parameters:</h3>
    <ul>
      <li><span class="parameter">item</span>
        <span class="types"><span class="type">value</span></span>
       a new value to be queued in the heap</li>
    </ul>

    <h3>Usage:</h3>
    <ul>
        <pre class="example">
 myHeap:push(1)
 -- or, with chaining
 myHeap:push(1):push(2):push(4)</pre>
    </ul>

    <h3>Returns:</h3>
    <ol>

          <span class="types"><a class="type" href="../modules/core.bheap.html#Class_heap">heap</a></span>
        self (the calling <a href="../modules/core.bheap.html#Class_heap">heap</a>  itself, can be chained)
    </ol>


</dd>
    <dt>
    <a name = "heap:pop"></a>
    <strong>heap:pop&nbsp;()</strong>
    </dt>
    <dd>
    Pops from the <a href="../modules/core.bheap.html#Class_heap">heap</a> .
 Removes and returns the lowest cost item (with respect to the comparison function being used) from the <a href="../modules/core.bheap.html#Class_heap">heap</a> .


    <h3>Usage:</h3>
    <ul>
        <pre class="example">
 while not myHeap:empty() do
   local lowestValue = myHeap:pop()
   ...
 end</pre>
    </ul>

    <h3>Returns:</h3>
    <ol>

          <span class="types"><span class="type">value</span></span>
        a value previously pushed into the heap
    </ol>


</dd>
    <dt>
    <a name = "heap:heapify"></a>
    <strong>heap:heapify&nbsp;( [item])</strong>
    </dt>
    <dd>
    Restores the <a href="../modules/core.bheap.html#Class_heap">heap</a>  property.
 Reorders the <a href="../modules/core.bheap.html#Class_heap">heap</a>  with respect to the comparison function being used.
 When given argument <strong>item</strong> (a value existing in the <a href="../modules/core.bheap.html#Class_heap">heap</a> ), will sort from that very item in the <a href="../modules/core.bheap.html#Class_heap">heap</a> .
 Otherwise, the whole <a href="../modules/core.bheap.html#Class_heap">heap</a>  will be cheacked.

    <h3>Parameters:</h3>
    <ul>
      <li><span class="parameter">item</span>
        <span class="types"><span class="type">value</span></span>
       the modified value</li>
    </ul>

    <h3>Usage:</h3>
    <ul>
        <pre class="example">myHeap:heapify()</pre>
    </ul>

    <h3>Returns:</h3>
    <ol>

          <span class="types"><a class="type" href="../modules/core.bheap.html#Class_heap">heap</a></span>
        self (the calling <a href="../modules/core.bheap.html#Class_heap">heap</a>  itself, can be chained)
    </ol>


</dd>
</dl>


</div> <!-- id="content" -->
</div> <!-- id="main" -->
<div id="about">
<i>generated by <a href="http://github.com/stevedonovan/LDoc">LDoc 1.2</a></i>
</div> <!-- id="about" -->
</div> <!-- id="container" -->
</body>
</html>
